package business;

import java.util.Vector;


public class ConvexHull {

    private Punto minimo = new Punto();
    
    public Poligono calcularPoligonoConvexo(Vector<Punto> puntos){
		
    	Poligono poligono = new Poligono();
    	
    	this.calcularMenorOrdenanda(puntos);
    	this.calcularArgumento(puntos);
    	this.ordenarQuicksort(puntos, 0, puntos.size()-1);
    	this.definirPuntosCH(puntos);
    	poligono = this.crearPoligono(puntos);
    	
    	return poligono;
    }
    
    private void calcularMenorOrdenanda(Vector<Punto> vector){
                            
            minimo.setCoordenadaY(vector.get(0).getCoordenadaY());
            minimo.setCoordenadaX(vector.get(0).getCoordenadaX());
            
            for (int i = 1; i<vector.size();i++)
            {
                    if (vector.get(i).getCoordenadaY()<minimo.getCoordenadaY())
                    {
                            minimo.setCoordenadaY(vector.get(i).getCoordenadaY());
                            minimo.setCoordenadaX(vector.get(i).getCoordenadaX());
                    }
            }
    }
    
    private void calcularArgumento(Vector<Punto> puntos){
            
            double xmin = minimo.getCoordenadaX();
            double ymin = minimo.getCoordenadaY();
            double xpt = 0;
            double ypt = 0;
            double arg = 0;
            
            for (int i = 0; i<puntos.size();i++)
            {
            	xpt =  puntos.get(i).getCoordenadaX();
                ypt =  puntos.get(i).getCoordenadaY();
                
            	if ( (xpt==0) && (ypt > 0) ){
            		arg = 90;
            	}
            	else if ( (xpt==0) && (ypt<0)){
            		arg = 270;
            	}
            	else{
            		if (ypt==ymin && xpt==xmin)
            			arg = 0;
            		else
            			arg = Math.atan((ypt-ymin)/(xpt-xmin))*180/Math.PI;
            		
            		if (xpt>0 && ypt < 0)
            		{
            			arg = arg + 360;
            		}
            		else if (xpt<0)
            		{
            			arg = arg + 180;
            		}
            	}
                    
                    puntos.get(i).setArgumento(arg);
            }
    }
    
    
    private void definirPuntosCH(Vector<Punto> vector){
    	
    	double xa,xb,xc,ya,yb,yc;
    	int i1,i2,i3;
    	double pcruz;
    	
    	for (int i=0; i < vector.size(); i++){
    		
    		i1 = i;
    		
    		if (i+1 < vector.size())
    			i2 = i+1;
    		else
    			i2 = i+1-vector.size();
    		
    		if (i+2 < vector.size())
    			i3 = i+2;
    		else
    			i3 = i+2-vector.size();
    				
    		xa = vector.get(i1).getCoordenadaX();
    		xb = vector.get(i2).getCoordenadaX();
    		xc = vector.get(i3).getCoordenadaX();
    		ya = vector.get(i1).getCoordenadaY();
    		yb = vector.get(i2).getCoordenadaY();
    		yc = vector.get(i3).getCoordenadaY();
    		
    		pcruz = (yc-yb)*(xa-xb)-(ya-yb)*(xc-xb);
    		
    		if (pcruz >= 0){
    			vector.remove(i2);
    			i--;
    		}
    	}
    }

    
    
    private void ordenarQuicksort(Vector<Punto> vector, int primero, int ultimo){
    	int i=primero, j=ultimo;
    	Double pivote = vector.get((primero + ultimo) / 2).getArgumento();
    	Punto auxiliar;
 
    	do{
    		while(vector.get(i).getArgumento()<pivote) i++;    		
    		while(vector.get(j).getArgumento()>pivote) j--;
 
    		if (i<=j){
    			auxiliar=vector.get(j);
    			vector.set(j, vector.get(i));
    			vector.set(i, auxiliar);
    			i++;
    			j--;
    		}
 
    	} while (i<=j);
 
    	if(primero<j) ordenarQuicksort(vector,primero, j);
    	if(ultimo>i) ordenarQuicksort(vector,i, ultimo);
    }
    
    private Poligono crearPoligono (Vector<Punto> puntos){
    	
    	Poligono poligono = new Poligono();
    	
    	Vector<Linea> linea = new Vector<Linea>();
    	for (int i = 0; i<puntos.size(); i++)
    	{
    		if (i<puntos.size()-1)
    			linea.add(new Linea(puntos.get(i),puntos.get(i+1)));
    		else
    			linea.add(new Linea(puntos.get(i),puntos.get(0)));
    	}
    	
    	poligono.setLineas(linea);
    	
    	return poligono;
    }

    public Punto getMinimo() {
            return minimo;
    }

    public void setMinimo(Punto minimo) {
            this.minimo = minimo;
    }
	
}
